package 力扣_二分查找.旋转数组系列;

/**
 * @author zx
 * @create 2022-08-24 12:31
 */
public class 搜索旋转排序数组_33 {
    /**
     * @return
     * 将数组一分为二,其中一定有一个是有序的,另一个可能是有序,也能是部分有序
     * 此时有序部分用二分法查找.无序部分再一分为二,其中一个一定有序,另一个可能有序,可能无序;就这样循环.
     *
     * 简单思路：始终去有序的那个范围内去找target,不在就去另一半无序的找,但是要将无序再次划分成有序然后再找...
     *
     * 1. 首先明白，旋转数组后，从中间划分，一定有一边是有序的。
     * 2. 由于一定有一边是有序的，所以根据有序的两个边界值来判断目标值在有序一边还是无序一边
     * 3. 这题找目标值，遇到目标值即返回
     * 4. 注意：由于有序的一边的边界值可能等于目标值，所以判断目标值是否在有序的那边时应该加个等号
     * (在二分查找某个具体值得时候如果把握不好边界值，可以再每次查找前判断下边界值，也就是while循环里面的两个if注释)
     * // if(nums[left] == target) return left;
     * // if(nums[right] == target) return right;
     * 上面这点太重要了！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
     *
     * 并且这道题要过全部测试用例,if()条件必须假定右边有序
     */
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                return mid;
            }
            //如果右边有序  搜索区间：[mid + 1,right]
            //注意：由于有序的一边的边界值可能等于目标值,所以判断目标值是否在有序的那边时应该加个等号
            if(nums[mid] < nums[right]){
                if(nums[mid] < target && target <= nums[right]){//目标值在右边
                    left = mid + 1;
                }else{//目标值在左边
                    right = mid - 1;
                }
            //如果左边有序  搜索区间：[left,mid - 1]
            }else{
            //}else if(nums[mid] > nums[left]){这样过不了
                if(nums[mid] > target && target >= nums[left]){//目标值在左边
                    right = mid - 1;
                }else{//目标值在右边
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
}
